package backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: june
 * @date: 2023/7/25
 * @description: 77. 组合
 * 
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 
 * 你可以按 任何顺序 返回答案。
 * 
 * 1 <= n <= 20
 * 1 <= k <= n
 * 
 * 回溯法的模板
 * void backtracking(参数) {
 * if (终止条件) {
 * 存放结果;
 * return;
 * }
 * 
 * for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
 * 处理节点;
 * backtracking(路径，选择列表); // 递归
 * 回溯，撤销处理结果
 * }
 * }
 **/

public class Combination_77 {
    // 保存最终的结果
    List<List<Integer>> result = new ArrayList<>();

    // 临时记录当前的组合
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrace(n, k, 1);
        return result;
    }

    private void backtrace(int n, int k, int startIndex) {
        if (path.size() == k) {
            // 这里必须要新建一个ArrayList添加到result中，因为最后path会被清空，引用传递使得result中的数据也是空的
            result.add(new ArrayList<>(path));
            return;
        }

        // 剪枝：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了
        // 接下来需要选择的个数 k - path.size()
        // 搜索起点的上界为 n - (k - path.size()) + 1
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtrace(n, k, i + 1);
            // 回溯，删除最后一个元素，从而可以反复使用path
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {

        Combination_77 combination_77 = new Combination_77();

        System.out.println(combination_77.combine(4, 2));
    }
}
